#include <iostream>
#include <string>
#include <climits>
#include <cmath>
#include <boost/dynamic_bitset.hpp>
#include <vector>
#include "szabo.cpp"

using namespace std;
using namespace boost;

double diffclock( clock_t clock1, clock_t clock2 ) {

        double diffticks = clock1 - clock2;
        double diffms    = diffticks / CLOCKS_PER_SEC;

        return diffms;
    }

/**
 * Megfeszíti a gráfot a kapott bitset alapján.
 * @param graph
 * @param colorclass
 * @return
 */
vector<dynamic_bitset<> > stretch_graph(vector<dynamic_bitset<> > graph, dynamic_bitset<> colorclass)
{
    int size = colorclass.size();           /** a színosztályok száma **/

    for(int i = 0; i < size; ++i) {
        if(colorclass[i]) {
            graph[i] = colorclass & graph[i];
        } else {
            graph[i].reset();
        }
    }
    return graph;
}

/**
 * Ugyanaz, mint a clq_search, annyi módosítással, hogy itt megszámolja,
 * hogy mennyi s-klikket alkot a kapott él.
 * @param graph
 * @param colorclass
 * @param s
 * @return
 */
int clq_search_count(vector<dynamic_bitset<> > graph, dynamic_bitset<> colorclass,  int s)
{
    vector<dynamic_bitset<> > stack;
    int top = 0;                          /** a stack top-ja **/
    int c = 0;                              /** az adott él mennyi s-klikket alkot **/
    int size = graph.size();                /** a gráf mérete **/
    stack.push_back(colorclass);

    do {
        for(int i = 0; i < size; ++i) {
            if(stack[top][i]) {
                stack[top][i] = 0;
                stack.push_back( stack[top++] & graph[i] );
                break;
            }
        }
        if(top >= s) {
            ++c;
            --top;
            stack.pop_back();
        }

        if(stack[top].none()) {
            --top;
            stack.pop_back();
        }
    } while(top >= 0);        ///kell vagy nem >=
    return c;
}

/**
 * S méretű klikket keres a kapott gráfban, a színosztály alapján.
 * Ha a colorclass változó csupa egyesből áll, akkor megmondja,
 * hogy van-e az egész gráfban S méretű klikk.
 * Ha colorclass egy tényleges színosztály, akkor megmondja,
 * hogy a kapott színosztályban található-e S méretű klikk.
 * @param graph
 * @param colorclass
 * @param s
 * @return
 */
bool clq_search(vector<dynamic_bitset<> > graph, dynamic_bitset<> colorclass,  int s)
{
    vector<dynamic_bitset<> > stack;
    int top = 0;                          /** a stack top-ja !!**/
    int size = graph.size();                /** a gráf mérete */
    stack.push_back(colorclass);

    do {
        for(int i = 0; i < size; ++i) {
            if(stack[top][i]) {
                stack[top][i] = 0;
                stack.push_back( stack[top++] & graph[i] );
                break;
            }
        }
        if(top >= s) {
            return true;
        }
        if(stack[top].none()) {
            --top;
            stack.pop_back();
        }
    } while(top >= 0);
    return false;
}

/**
 * Kiszínezi a kapott gráfot s színnel.
 * Egy csúcs akkor tehető bele egy színosztályba, ha nem alkot benne s-klikket.
 * Ebből adódóan a program egy mohó színező, mivel amint talált a csúcsnak egy
 * olyan színosztályt, amelyben nem alkot s-klikket beleteszi, és ugrik a következő csúcsra.
 * Ha nem talált olyan színosztályt, amibe beletudta volna tenni, akkor nyit egy új,
 * üres színosztályt neki, és ugrik a következő csúcsra.
 * @param graph
 * @param colorclasses
 * @param s
 */
void s_clique_coloring(vector<dynamic_bitset<> > graph, vector<dynamic_bitset<> >& colorclasses, int s)
{
    int size = graph.size();                /** a gráf mérete **/
    int node = 0;
    boost::dynamic_bitset<> temp( size );
    if(node < s - 1) {
        while(node < s-1) {
            temp[node++] = 1;
        }
        colorclasses.push_back( temp );
    }
    do {
        int cr = 0;
        int colors=colorclasses.size();     /** az aktuális színek száma **/
        do {
//        if(k_clique(stretch_graph(graph, colorclasses[cr] & graph[node]), s-1) == false) {
//            colorclasses[cr][node++] = 1;
//            break;
//        }
            if(clq_search( graph, colorclasses[cr] & graph[node], s-1) == false) {
                colorclasses[cr][node++] = 1;
                break;
            }
            ++cr;
        } while(cr < colors);

        if(cr == colors) {
            temp.reset();
            temp[node]=1;
            ++node;
            colorclasses.push_back( temp );
        }
    } while( node < size );

}

/**
 * Átrendezi a gráfot a kapott színosztályok alapján.
 * Olyan sorrendben helyezi el a csúcsokat, ahogy azok megtalálhatóak
 * a színosztályokban, ez a pbm fájl elkészítésekor használatos függvény.
 * Segítségével lesz jól látható a színezés eredménye.
 * @param graph
 * @param colorclasses
 */
void sorting(vector<dynamic_bitset<> >& graph, vector<dynamic_bitset<> > colorclasses)
{
    int size = graph.size();                /** a gráf mérete **/
    int colors = colorclasses.size();       /** a színek száma **/
    vector<int> sorrend;
    vector<boost::dynamic_bitset<> > graph0;

    for(int i = 0; i < colors; ++i) {
        for(int j = 0; j < size; ++j) {
            if(colorclasses[i][j]) {
                sorrend.push_back(j);
            }
        }
    }

    for(int i = 0; i < size; ++i) {
        boost::dynamic_bitset<> temp;
        for(int j = 0; j < size; ++j) {
            temp.push_back(graph[sorrend[i]][sorrend[j]]);
        }
        graph0.push_back(temp);
    }
    graph=graph0;
}//end sorting

/**
 * A kapott színosztályokat csökkenő sorba rendezi a bennük levő csúcsok alapján.
 * Segítségével egyszerűen letudjuk vágni az első K legnagyobb színosztályt.
 * @param colorclasses
 */
void bubble_sort(vector<dynamic_bitset<> >& colorclasses)
{
    int flag = 1;
    boost::dynamic_bitset<> temp;
    int colors = colorclasses.size();       /** a színek száma **/

    for(int i = 1; (i <= colors) && flag; i++) {
        flag = 0;
        for (int j = 0; j < (colors -1); j++) {
            if (colorclasses[j+1].count() > colorclasses[j].count()) {
                temp = colorclasses[j];
                colorclasses[j] = colorclasses[j+1];
                colorclasses[j+1] = temp;
                flag = 1;
            }
        }
    }
}

/**
 * Megmondja, hogy a kapott csúcs melyik színosztályban alkot kevesebb élt.
 * Segítségével jól eltudjuk osztani a kisebb színosztályok csúcsait
 * a nagyobb színosztályok között.
 * @param node
 * @param colors_bigger
 * @param graph
 * @return
 */
int min_edges(int node, vector<dynamic_bitset<> > colors_bigger, vector<dynamic_bitset<> > graph)
{
    int index;                              /** annak a színosztálynak az indexe, ahova majd betesszük a csúcsot **/
    int min = INT_MAX;                      /**  **/
    int colors = colors_bigger.size();
    vector<int> sum_edges;

    for(int i = 0; i < colors; ++i) {
        sum_edges.push_back( (graph[node] & colors_bigger[i]).count() );
    }

    for(int i = 0; i < colors; ++i) {
        if(sum_edges[i] < min) {
            min = sum_edges[i];
            index = i;
        }
    }

    return index;
}

/**
 * Elosztja a színosztályokat K szerint.
 * Először sorbarendezi a színosztályokat a méretük alapján: bubble_sort()
 * Majd minden egyes, a kisebb színosztályban levő csúcsra megnézi, hogy
 * melyik nagoybb színosztályban alkot kevesebb élt: min_edges()
 * ?? Egy jó megoldás lehet az is, ha abba az osztályba tesszük, amelyikben kevesebb s-klikket alkot
 * aggregate, reclassify...
 * @param graph
 * @param colorclasses
 * @param k
 */
void reclassify(vector<dynamic_bitset<> > graph, vector<dynamic_bitset<> >& colorclasses, const int q, const int s)
{
    int size = graph.size();                    /** a gráf mérete **/
    int num_of_bigger_classes=0;                /** a nagyobb színosztályok száma lesz **/
    int colors=colorclasses.size();             /** a színek száma **/
    //int k = (q-1)%(s-1) ? (q-1)/(s-1) +1 : (q-1)/(s-1);                 /** mekkorára osztjuk szét a színosztályokat **/
    int k;
    for (k=1; k*(s-1) < q; ++k);
    --k;

    vector<dynamic_bitset<> > colors_bigger;
    vector<dynamic_bitset<> > colors_smaller;

    bubble_sort(colorclasses);

    while(num_of_bigger_classes < k) {
        colors_bigger.push_back(colorclasses[num_of_bigger_classes++]);
    }
    while(num_of_bigger_classes < colors) {
        colors_smaller.push_back(colorclasses[num_of_bigger_classes++]);
    }

    int num_of_smaller_classes = colors_smaller.size(); /** a kisebb színosztályok száma **/
    for(int i = 0; i < num_of_smaller_classes; ++i) {
        int index;
        for(int j = 0; j < size; ++j) {
            if(colors_smaller[i][j]) {
                index = min_edges(j, colors_bigger, graph);
                colors_bigger[index][j]=1;
            }
        }
    }
    colorclasses = colors_bigger;
}
